package day_2022_12_to_3.year2023;
import java.util.*;
/**
 * @author haomin
 * @date 2023/04/08 22:41
 **/
public class Day4_8_Num1125 {
    class Solution {
        public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
            Map<String, Integer> map=new HashMap<String, Integer>();
            int n=req_skills.length;
            for(int i=0;i<n;i++) {
                map.put(req_skills[i], i);
            }
            int m=1<<n;
            int b=Integer.MAX_VALUE;
            int[][] p=new int[m][2];
            int[] dp=new int[m];
            Arrays.fill(dp, b);
            dp[0]=0;
            int len=people.size();
            for(int k=0;k<len;k++) {
                List<String> pp=people.get(k);
                for(int i=1;i<m;i++) {
                    int tmp=i;
                    for(String s:pp) {
                        int t=map.get(s);
                        if((tmp&(1<<t))!=0) {
                            tmp^=(1<<t);
                        }
                    }
                    if(dp[tmp]==b) {
                        continue;
                    }
                    if(dp[i]>dp[tmp]+1) {
                        dp[i]=dp[tmp]+1;
                        p[i][0]=tmp;
                        p[i][1]=k;
                    }
                }
            }
            List<Integer> res=new ArrayList<Integer>();
            for(int i=m-1;;) {
                res.add(p[i][1]);
                i=p[i][0];
                if(i==0) {
                    break;
                }
            }
            int rs=res.size();
            int[] ans=new int[rs];
            for(int i=0;i<rs;i++) {
                ans[i]=res.get(i);
            }
            return ans;
        }
    }
}